import random


def backtrack(nums, path, res, k):
    """
    回溯法生成排列或组合

    Args:
        nums: 原始数组
        path: 当前生成的排列或组合
        res: 结果列表，用于存储所有可能的排列或组合
        k: 需要生成的长度（排列）或组合的元素个数（组合）
        
    Core Idea:
        - 使用回溯法，通过递归的方式生成排列或组合。
        - 在每一层递归中，从原始数组中选择一个数字，并添加到当前排列或组合中。
        - 当生成的排列或组合长度达到要求时，将其加入结果列表中。
        - 递归结束后，撤销选择，回溯到上一层，继续探索其他可能的选择。
    """
    # 结束条件：当前生成的排列或组合长度达到要求
    if len(path) == k:
        res.append(path[:])
        return

    # 遍历选择列表
    for i in range(len(nums)):
        # 剪枝条件：当前数字已经在排列或组合中，跳过该数字
        if nums[i] in path:
            continue

        # 做出选择
        path.append(nums[i])

        # 递归进入下一层决策树
        backtrack(nums, path, res, k)

        # 撤销选择，回溯到上一层
        path.pop()

def generate_permutations(nums):
    """
    生成给定数组的全排列

    Args:
        nums: 原始数组
        
    Core Idea:
        - 调用 backtrack 函数生成给定数组的全排列。
        - 全排列的长度与原始数组的长度相同。
    """
    res = []
    backtrack(nums, [], res, len(nums))
    return res

def generate_combinations(nums, k):
    """
    生成给定数组的所有组合

    Args:
        nums: 原始数组
        k: 组合的元素个数
        
    Core Idea:
        - 调用 backtrack 函数生成给定数组的所有组合。
        - 组合的长度为 k。
    """
    res = []
    backtrack(nums, [], res, k)
    return res

if __name__ == "__main__":
    # 生成随机输入列表
    nums = random.sample(range(1, 10), 4)
    k = random.randint(1, 4)

    print("Input:")
    print("nums =", nums)
    print("k =", k)

    # 生成全排列并打印结果
    permutations = generate_permutations(nums)
    print("\nPermutations:")
    for perm in permutations:
        print(perm)
    
    print("Total permutations:", len(permutations))

    # 生成组合并打印结果
    combinations = generate_combinations(nums, k)
    print("\nCombinations of size", k, ":")
    for comb in combinations:
        print(comb)
        
    print("Total combinations of size", k, ":", len(combinations))